
//排序
void sort()
{
    Fastsort(0,size-1,0,2*log2(size));
}
void Fastsort(size_t start,size_t end,size_t curdepth,size_t maxdepth)
{
    if(start>=end)
        return;
    if(curdepth<=maxdepth)
     {
         size_t par=partition(size_t start,size_t end);
        if(par!=0)
            Fastsort(start,par-1,curdepth+1,maxdepth);
        Fastsort(par+1,end,curdepth+1,maxdepth);

     }  

     else   
     {
        insertsort(size_t start,size_t end);
     } 
}
void partition(size_t start,size_t end)
{
    size_t left=start;
    size_t right=end;
    ElementType tmp=array[left];
    while(left<right)
    {
        while(a[right]>tmp&&left<right)
            right--;
        if(left<right)
            a[left++]=a[right];
        while(a[left]<tmp&&left<right)
            left++
        if(left<right)
            a[right--]=a[left];
    }
    a[left]=tmp;
    return left;

}
void insertSort(size_t start,size_t end)
{
    for(size_t i=start+1;i<=end;i++)
    {
        size_t j=i;
        size_t tmp=array[i];
        for(;j>start;j--)
        {
            if(tmp<a[j-1])
                a[j]=a[j-1];
            else
                break;
        }
    }
    a[j]=tmp;
}

//并集
void bingji(const  DynamicArray &a)
{
    DynamicArray result;
    int first=0;
    int seconde=0;
    while(first<this->size&&seconde<a.size)
    {
        if(array[first]==a[seconde])
            {result.insertail(first++);
            seconde++;}
        else if(array[first]>a[seconde])
        {
            result.insertail(seconde++);
        }
        else if(array[first]<a[seconde])
        {
            result.insertail(first++);
        }
    }
    while(first<this->size)
    {
        result.inserttail(first++);
    }
    while(seconde<a.size)
    {
        result.inserttail(seconde++);
    }
    return result;
}
//二分查找
size_t Binarysearch(const ElementType& element)
{
    size_t left=0;
    size_t right=size-1;
    while(left<=right)
    {
        mid=left+(right-left)/2;
        if(array[mid]==element)
            return mid;
        else if(array[mid]>element)
          {  if(mid==0)
                return Ulong_max;
            right=mid-1
          }
        else if(array[mid]<element)
            left=mid+1;
    }
    return ulong_max;

}